package com.cjl.daily;

import org.junit.jupiter.api.Test;

import java.util.*;

public class DailyQuestion {

    /**
     * 2578. 最小和分割
     *
     * @param num
     * @return
     */
    public int splitNum(int num) {
        // 将这个整数转字符数组方便后续运算
        char[] chars = Integer.toString(num).toCharArray();
        // 数组排序
        Arrays.sort(chars);
        // 直接定义num1和num2
        int num1 = 0, num2 = 0;
        // 遍历填充num1和num2
        for (int i = 0; i < chars.length; i++) {
            // 利用num中较小的数字填充num1和num2中的高位,以得到最小的num1和num2
            if (i % 2 == 0) {
                num1 = num1 * 10 + (chars[i] - '0');
            } else {
                num2 = num2 * 10 + (chars[i] - '0');
            }
        }
        return num1 + num2;
    }

    /**
     * 2731. 移动机器人
     *
     * @param nums
     * @param s
     * @param d
     * @return
     */
    public int sumDistance(int[] nums, String s, int d) {
        int len = nums.length;
        // 每个机器人的最终位置数组
        long[] position = new long[len];
        // 每个机器人都按照指定方向移动d步
        for (int i = 0; i < len; i++) {
            position[i] = (long) nums[i] + (s.charAt(i) == 'L' ? -d : d);
        }
        // 数组排序
        Arrays.sort(position);
        int res = 0;
        int mod = (int) 1e9 + 7;
        for (int i = 1; i < len; i++) {
            res += (position[i] - position[i - 1]) * i % mod * (len - i) % mod;
            res %= mod;
        }
        return (int) res;
    }

    /**
     * 2512. 奖励最顶尖的 K 名学生
     *
     * @param positive_feedback
     * @param negative_feedback
     * @param report
     * @param student_id
     * @param k
     * @return
     */
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        // 定义hashSet存储正向和负面单词
        HashSet<String> positive = new HashSet<>();
        HashSet<String> negative = new HashSet<>();
        // 填充以上两个集合
        Collections.addAll(positive, positive_feedback);
        Collections.addAll(negative, negative_feedback);
        // 定义二维数组存储每个学生id和对应分数
        int len = report.length;
        // 其中每一项,第一项为学生id,第二项为对应分数
        int[][] arr = new int[len][2];
        for (int i = 0; i < len; i++) {
            // 学生id
            int sid = student_id[i];
            // 学生分数
            int score = 0;
            // 分割当前学生的评语
            for (String s : report[i].split(" ")) {
                if (positive.contains(s)) {
                    score += 3;
                } else if (negative.contains(s)) {
                    score -= 1;
                }
            }
            // 加入arr数组
            arr[i] = new int[]{sid, score};
        }
        // 根据分数进行排序,如果分数相同则按照学号进行排序
        /*Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] == b[1] ? a[0] - b[0] : b[1] - a[1];
            }
        });*/
        Arrays.sort(arr, (a, b) -> a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(arr[i][0]);
        }
        return res;
    }

    /**
     * @param nums
     * @return
     */
    public long findTheArrayConcVal(int[] nums) {
        long sum = 0;
        // 循环拼接数组
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            sum += Long.parseLong(nums[left] + "" + nums[right]);
            left++;
            right--;
        }
        if (left == right) {
            sum += nums[left];
        }
        return sum;
    }

    /**
     * @param rains
     * @return
     */
    public int[] avoidFlood(int[] rains) {
        // 定义set存储不下雨的日期
        TreeSet<Integer> set = new TreeSet<>();
        // 定义map存储下雨的对应日期  key:下雨的池塘 value:下雨的日期
        HashMap<Integer, Integer> map = new HashMap<>();
        // 初始化ans数组
        int[] ans = new int[rains.length];
        Arrays.fill(ans, 1);
        // 开始循环
        for (int i = 0; i < rains.length; i++) {
            // 当天下雨的池塘,如果为0,则是晴天
            int rain = rains[i];
            if (rain == 0) { // 将晴天的日期存入set中
                set.add(i);
            } else { // 这天下雨
                ans[i] = -1;
                // 判断是否是第一次下雨
                if (map.containsKey(rain)) { // 不是第一次
                    // 获取大于该池塘下雨的最小日期进行排水
                    Integer date = map.get(rain);
                    Integer minDate = set.ceiling(date);
                    if (minDate == null) { // 没有找到可排水日期,洪水不可避免
                        return new int[0];
                    }
                    // 找到直接排水,这天设置的排水池塘为rain
                    ans[minDate] = rain;
                    set.remove(minDate);
                }
                // 是第一次,直接加入
                map.put(rain, i);
            }
        }
        return ans;
    }

    /**
     * 136. 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }

    /**
     * 137. 只出现一次的数字Ⅱ
     *
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }

    public int[] singleNumber3(int[] nums) {
        // 1.数组整体异或找出两个不同的元素的异或值
        int a = 0;
        int b = 0;
        // xor为a和b的异或值
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        // 2.定义div为两个元素不同的那一位
        int div = 1;
        while ((div & xor) == 0) {
            // div左移一位
            div <<= 1;
        }
        // 3.根据div对nums进行分组，分别异或出a，b
        for (int i = 0; i < nums.length; i++) {
            // 分组
            if ((nums[i] & div) == 0) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        return new int[]{a, b};
    }

    /**
     * 2652. 倍数求和
     *
     * @param n
     * @return
     */
    public int sumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }


    /**
     * 2530. 执行 K 次操作后的最大分数
     *
     * @param nums
     * @param k
     * @return
     */
    public long maxKelements(int[] nums, int k) {
        heapify(nums); // 原地堆化（最大堆）
        long ans = 0;
        while (k-- > 0) {
            ans += nums[0]; // 堆顶
            nums[0] = (nums[0] + 2) / 3;
            sink(nums, 0); // 堆化（只需要把 nums[0] 下沉）
        }
        return ans;
    }

    // 原地堆化（最大堆）
    // 堆化可以保证 h[0] 是堆顶元素，且 h[i] >= max(h[2*i+1], h[2*i+2])
    private void heapify(int[] h) {
        // 下标 >= h.length / 2 的元素是二叉树的叶子，无需下沉
        // 倒着遍历，从而保证 i 的左右子树一定是堆，那么 sink(h, i) 就可以把左右子树合并成一个堆
        for (int i = h.length / 2 - 1; i >= 0; i--) {
            sink(h, i);
        }
    }

    // 把 h[i] 不断下沉，直到 i 的左右儿子都 <= h[i]
    private void sink(int[] h, int i) {
        int n = h.length;
        while (2 * i + 1 < n) {
            int j = 2 * i + 1; // i 的左儿子
            if (j + 1 < n && h[j + 1] > h[j]) { // i 的右儿子比 i 的左儿子大
                j++;
            }
            if (h[j] <= h[i]) { // 说明 i 的左右儿子都 <= h[i]，停止下沉
                break;
            }
            swap(h, i, j); // 下沉
            i = j;
        }
    }

    // 交换 h[i] 和 h[j]
    private void swap(int[] h, int i, int j) {
        int tmp = h[i];
        h[i] = h[j];
        h[j] = tmp;
    }

    /**
     * @param nums
     * @return
     */
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 所有元素两两相乘，得到一个数对
                int key = nums[i] * nums[j];
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }
        int count = 0;
        for (Integer value : map.values()) {
            // 取到一个合法的组合就可以得到四个元组，则利用排列公式可以得出以下计算
            count += value * (value - 1) * 4;
        }
        return count;
    }

    /**
     * 2525. 根据规则将箱子分类
     *
     * @param length
     * @param width
     * @param height
     * @param mass
     * @return
     */
    public String categorizeBox(int length, int width, int height, int mass) {
        int max = Math.max(length, Math.max(width, height));
        long volume = (long) length * width * height;
        boolean Bulky = max >= 1e4 || volume >= 1e9;
        boolean Heavy = mass > 100;
        if (mass >= 100) {
            Heavy = true;
        }
        if (Bulky && Heavy) {
            return "Both";
        } else if (Bulky) {
            return "Bulky";
        } else if (Heavy) {
            return "Heavy";
        } else {
            return "Neither";
        }
    }

    /**
     * 2316. 统计无向图中无法互相到达点对数
     *
     * @param n
     * @param edges
     * @return
     */
    public long countPairs(int n, int[][] edges) {
        // 定义list集合存储每条边的关系
        List<Integer>[] g = new List[n];
        boolean[] vis = new boolean[n];
        // 把g中设置每一个元素设置成arrayList
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int a = e[0];
            int b = e[1];
            // 表示这两个点相互可以到达
            g[a].add(b);
            g[b].add(a);
        }
        // 无法互相到达的不同点对数目。
        long res = 0;
        // 之前所有联通分量的节点个数
        long s = 0;
        for (int i = 0; i < n; i++) {
            // 深度优先遍历这个节点
            // t为每个联通分量的节点个数
            int t = countPairsDFS(i, g, vis);
            // 累加这次连通分量与之前所形成的不可到达的节点个数
            res += s * t;
            // 更新之前联通分量总节点个数
            s += t;
        }
        return res;
    }

    private int countPairsDFS(int i, List<Integer>[] g, boolean[] vis) {
        // 判断这个节点访问过没有
        if (vis[i]) {
            return 0;
        }
        // 没访问过先标记，然后访问
        vis[i] = true;
        // 计数
        int count = 1;
        // 遍历所有这个节点能到达的点
        for (Integer j : g[i]) {
            count += countPairsDFS(j, g, vis);
        }
        // 返回这个连通分量的节点个数
        return count;
    }

    /**
     * 1402. 做菜顺序
     *
     * @param satisfaction
     * @return
     */
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int f = 0;
        int s = 0;
        for (int i = satisfaction.length - 1; i >= 0; i--) {
            s += satisfaction[i];
            // 只要s不为负就一直加到f中
            if (s <= 0) {
                break;
            }
            f += s;
        }
        return f;
    }

    /**
     * 2678. 老人的数目
     *
     * @param details
     * @return
     */
    public int countSeniors(String[] details) {
        int count = 0;
        for (String detail : details) {
            Integer age = Integer.valueOf(detail.substring(11, 13));
            System.out.println(age);
            if (age > 60) {
                count++;
            }
        }
        return count;
    }

    /**
     * 1155. 掷骰子等于目标和的方法数
     *
     * @param n
     * @param k
     * @param target
     * @return
     */
    public int numRollsToTarget(int n, int k, int target) {
        int mod = (int) (1e9 + 7);
        // dp数组含义,dp[i,j]表示i个骰子且数字之和为j的方案有几种
        int[][] dp = new int[n + 1][target + 1];
        // 初始化(0个骰子投出和为0的方案有一种)
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) { // 骰子个数
            for (int j = 0; j <= target; j++) { // 目标和
                for (int x = 1; x <= k; x++) { // 每个骰子的点数
                    if (j - x >= 0) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % mod;
                    }
                }
            }
        }
        return dp[n][target];
    }

    /**
     * 2520. 统计能整除数字的位数
     *
     * @param num
     * @return
     */
    public int countDigits(int num) {
        int n = num;
        int count = 0;
        while (n > 0) {
            int x = n % 10;
            if (num % x == 0) {
                count++;
            }
            n /= 10;
        }
        return count;
    }

    /**
     * 2558. 从数量最多的堆取走礼物
     *
     * @param gifts
     * @param k
     * @return
     */
    public long pickGifts(int[] gifts, int k) {
        // 创建大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        // 将元素存入堆中
        for (int gift : gifts) {
            queue.offer(gift);
        }
        // 将大根堆中的元素取出并求根放回
        while (k-- > 0) {
            Integer x = queue.poll();
            queue.offer((int) Math.sqrt(x));
        }
        // 此时取出求和即可
        int res = 0;
        while (!queue.isEmpty()) {
            res += queue.poll();
        }
        return res;
    }

    /**
     * 421. 数组中两个数的最大异或值
     *
     * @param nums
     * @return
     */
    public int findMaximumXOR(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length - 1; i++) {
            int temp = nums[i];
            for (int j = 0; j < nums.length; j++) {
                temp ^= nums[j];
                max = Math.max(temp, max);
            }
        }
        return max;
    }

    /**
     * 187. 重复的DNA序列
     *
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences(String s) {
        ArrayList<String> res = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String str = s.substring(i, i + 10);
            map.put(str, map.getOrDefault(str, 0) + 1);
            if (map.get(str) == 2) {
                res.add(str);
            }
        }
        return res;
    }

    /**
     * 318. 最大单词长度乘积
     *
     * @param words
     * @return
     */
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        // 构造masks判断是否有重复字符
        for (int i = 0; i < n; i++) {
            String word = words[i];
            int length = word.length();
            for (int j = 0; j < length; j++) {
                // 把相应的出现过的字符串都设置为1
                masks[i] |= (1 << (word.charAt(j) - 'a'));
            }
        }
        int len = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) { // 没有重复字符
                    len = Math.max(len, words[i].length() * words[j].length());
                }
            }
        }
        return len;
    }

    /**
     * 2586. 统计范围内的元音字符串数
     *
     * @param words
     * @param left
     * @param right
     * @return
     */
    public int vowelStrings(String[] words, int left, int right) {
        int count = 0;
        HashSet<Character> set = new HashSet<>();
        Collections.addAll(set, 'a', 'e', 'i', 'o', 'u');
        for (int i = left; i <= right; i++) {
            String word = words[i];
            char c1 = word.charAt(0);
            char c2 = word.charAt(word.length() - 1);
            if (set.contains(c1) && set.contains(c2)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 2609. 最长平衡子字符串
     *
     * @param s
     * @return
     */
    public int findTheLongestBalancedSubstring(String s) {
        int res = 0;
        // 定义count数组用于统计连续出现的0和1的个数
        int[] count = new int[2];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                // 如果遇到的是1则count数组1的位置+1，同时更新最长的平衡子串
                count[1]++;
                res = Math.max(res, 2 * Math.min(count[0], count[1]));
            } else if (i == 0 || s.charAt(i - 1) == '1') {
                // 如果当前的字符是首位或者前一位是1则重置count数组
                count[0] = 1;
                count[1] = 0;
            } else {
                // 此时一定是0
                count[0]++;
            }
        }
        return res;
    }

    /**
     * 2300. 咒语和药水的成功对数
     *
     * @param spells
     * @param potions
     * @param success
     * @return
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int len = spells.length;
        int[] pairs = new int[len];
        for (int i = 0; i < len; i++) {
            int spell = spells[i];
            int count = 0;
            for (int j = 0; j < potions.length; j++) {
                if ((long) spell * potions[j] >= success) {
                    count++;
                }
            }
            pairs[i] = count;
        }
        return pairs;
    }


    @Test
    public void test() {
        System.out.println(countSeniors(new String[]{"7868190130M7522", "5303914400F9211", "9273338290F4010"}));
    }

}


/**
 * 901. 股票价格跨度
 */
class StockSpanner {
    private final Stack<int[]> stack;

    public StockSpanner() {
        // 初始化一个栈,栈中的元素放入一个数组,数字第一项为当前的price,第二项为这一项的跨度
        stack = new Stack<>();
    }

    public int next(int price) {
        // 当天的跨度至少为1
        int span = 1;
        // 只要当前栈不为空并且当前价格大于等于栈顶价格,则弹出,并加上当前跨度
        while (!stack.isEmpty() && price >= stack.peek()[0]) {
            span += stack.pop()[1];
        }
        // 当前价格入栈
        stack.push(new int[]{price, span});
        return span;
    }
}

/**
 * 307. 区域和检索 - 数组可修改
 */
class NumArray {
    private int[] sum; // sum[i] 表示第 i 个块的元素和
    private int size; // 块的大小
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        size = (int) Math.sqrt(n);
        sum = new int[(n + size - 1) / size]; // n/size 向上取整
        for (int i = 0; i < n; i++) {
            sum[i / size] += nums[i];
        }
    }

    public void update(int index, int val) {
        sum[index / size] += val - nums[index];
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        int b1 = left / size, i1 = left % size, b2 = right / size, i2 = right % size;
        if (b1 == b2) { // 区间 [left, right] 在同一块中
            int sum = 0;
            for (int j = i1; j <= i2; j++) {
                sum += nums[b1 * size + j];
            }
            return sum;
        }
        int sum1 = 0;
        for (int j = i1; j < size; j++) {
            sum1 += nums[b1 * size + j];
        }
        int sum2 = 0;
        for (int j = 0; j <= i2; j++) {
            sum2 += nums[b2 * size + j];
        }
        int sum3 = 0;
        for (int j = b1 + 1; j < b2; j++) {
            sum3 += sum[j];
        }
        return sum1 + sum2 + sum3;
    }

    /**
     * 2697. 字典序最小回文串
     *
     * @param s
     * @return
     */
    public String makeSmallestPalindrome(String s) {
        char[] chars = s.toCharArray();
        // 定义双指针
        int left = 0;
        int right = chars.length - 1;
        while (left < right) {
            // 判断双指针指向的位置是否相同，如果相同则不操作，如果不相同则替换成字典数小的那个
            if (chars[left] != chars[right]) {
                chars[left] = chars[right] = (char) Math.min(chars[left], chars[right]);
            }
            // 移动双指针
            left++;
            right--;
        }
        return new String(chars);
    }

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        // start == nums.length 说明所有元素都比target小
        // nums[start] != target 说明这个数不存在数组中
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    // 求target在nums中第一次出现的位置
    // 输入：nums = [5,7,7,8,8,10], target = 8
    // 闭区间写法
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 206. 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 保存之前的next
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode leftNode = pre.next;
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        ListNode succ = rightNode.next;
        pre.next = null;
        rightNode.next = null;
        reverse(leftNode);
        pre.next = rightNode;
        leftNode.next = succ;
        return dummy.next;
    }
    public void reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 保存之前的next
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

